import List from "./List";
import IllegalArgumentException from "../exceptions/IllegalArgumentException";
import Obj, {equalsTo} from "../core/Obj";
import Comparator from "../utils/Comparator";
import FullCapacityException from "../exceptions/FullCapacityException";
import Collections from "../utils/Collections";
import PriorityQueue from "../queue/PriorityQueue";
import {hashArray} from "../core/Hash";

/**
 * List接口的可调整大小的数组实现。 实现所有可选的列表操作。
 *
 * size、isEmpty、get、set和迭代器操作在恒定时间内运行。add操作在分摊常数时间内运行，即添加n个元素需要O(n)时间。所有其他操作都在线性时间内运
 * 行（粗略地说）。
 *
 * 每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终不小于列表大小。当元素添加到ArrayList时，它的大小会自动增长但容量
 * 不会增长，但您可以手动增加它。
 *
 * @param E 存储在此列表中的元素类型
 * @version 1.0
 */
export default class ArrayList<E> extends Obj implements List<E> {

  /**
   * 一个数组的容器，用于存储元素。
   *
   * @private
   * @version 1.0
   */
  private readonly _elements: E[];

  /**
   * 此列表可以存储的元素数量。
   *
   * @private
   * @version 1.0
   */
  private _capacity: number;

  /**
   * 构造一个具有默认元素和容量的 ArrayList。
   *
   * 如果您不提供默认元素，它将不包含任何内容。 如果您不提供默认容量，它会将容量设置为无限。
   *
   * @param elements 需要默认置入此列表的元素
   * @param capacity 此列表的容量
   * @throws {FullCapacityException} 这个列表无法容纳这些元素
   * @throws {IllegalArgumentException} 这个容量数字不正确
   * @version 1.0
   */
  public constructor(elements: E[] = [], capacity: number = -1) {
    super();

    if (capacity !== -1 && elements.length > capacity) {
      throw new FullCapacityException(ArrayList.name, capacity);
    }

    if (capacity < -1) {
      throw new IllegalArgumentException("capacity should be bigger than -1");
    }

    this._elements = elements;
    this._capacity = capacity;
  }

  [Symbol.iterator](): Iterator<E> {
    return this.iterator();
  }

  /**
   * 将指定的元素附加到此列表的末尾。
   *
   * @param e 需要在加入此列表的元素
   * @return {boolean} 永远是true
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public add(e: E): boolean {
    if (!this.isFull()) {
      this._elements.push(e);
      return true;
    } else {
      throw new FullCapacityException(ArrayList.name, this._capacity);
    }
  }

  /**
   * 在此列表中的指定位置插入指定元素。 将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）。
   *
   * @param index 要插入的索引
   * @param e 要插入的火元素
   * @throws {IndexOutOfBoundException} 索引不符合要求
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public addByIndex(index: number, e: E): void {
    if (!this.isFull()) {
      const newIndex = Collections.accurateIndex(this, index);
      for (let i = this._elements.length - 1; i >= newIndex; i--) {
        this._elements[i + 1] = this._elements[i];
      }
      this._elements[newIndex] = e;
    } else {
      throw new FullCapacityException(ArrayList.name, this._capacity);
    }
  }

  /**
   * 返回此集合的容量。
   *
   * @return {number} 返回此结合的容量
   * @version 1.0
   */
  public capacity(): number {
    return this._capacity;
  }

  /**
   * 清空此集合。
   *
   * @version 1.0
   */
  public clear(): void {
    this._elements.splice(0);
  }

  /**
   * 返回此列表是否包含指定的元素。
   *
   * @param e 需要查找的元素
   * @return {boolean} 如果此列表包含该元素，则返回true，否则返回false
   * @version 1.0
   */
  public contains(e: E): boolean {
    return this.indexOf(e) !== -1;
  }

  public equals(b: Obj): boolean {
    if (b instanceof ArrayList) {
      return Collections.equals(this, b);
    }
    return false;
  }

  /**
   * 返回在此列表对应索引位置的元素。
   *
   * @param index 需要取元素的索引
   * @return {E} 此列表中对饮元素位置的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public get(index: number): E {
    const newIndex = Collections.accurateIndex(this, index);
    return this._elements[newIndex];
  }

  /**
   * 增加此列表的容量使其可以容纳更多的元素。
   *
   * 给出的容量必须比现有的容量更大，否则将会抛出{@link IllegalArgumentException}。当容量被设定为-1时，表示此列表容量无穷大，之后将不能再增
   * 加容量，也将不再判断容量是否充满。
   *
   * @param capacity 新的容量
   * @throws {IllegalArgumentException} 新的容量比当前容量小或容量已无法增长
   */
  public grow(capacity: number): boolean {
    if (capacity < this._capacity && capacity !== -1) {
      throw new IllegalArgumentException(
        "capacity " + capacity + " is smaller than current capacity " + this._capacity + " and is not -1");
    } else {
      this._capacity = capacity;
      return true;
    }
  }

  public hashCode(): number {
    return hashArray(this._elements);
  }

  /**
   * 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
   *
   * @param e 与需要寻找的元素相等的元素
   * @return {number} 此列表中指定元素第一次出现的索引，如果此列表没有，则为 -1
   * @version 1.0
   */
  public indexOf(e: E): number {
    let index = -1;
    for (let i = 0; i < this._elements.length; i++) {
      if (equalsTo(e, this._elements[i])) {
        index = i;
        break;
      }
    }
    return index;
  }

  /**
   * 返回此列表是否为空。
   *
   * @return {boolean} 如果此列表不包含任何元素，则返回true，否则返回false
   * @version 1.0
   */
  public isEmpty(): boolean {
    return this._elements.length === 0;
  }

  /**
   * 返回此列表是否已满。
   *
   * @return {boolean} 如果此列表存储的元素已到达容量，则返回true，否则返回false。若容量为-1，则永远不会满容量
   */
  public isFull(): boolean {
    return this._elements.length === this._capacity;
  }

  /**
   * 返回由列表内所有元素组成的迭代器。
   *
   * @return {Iterator<E>} 一个由列表内所有元素组成的迭代器
   * @see Iterator
   * @version 1.0
   */
  public iterator(): Iterator<E> {
    return this._elements[Symbol.iterator]();
  }

  /**
   * 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1。
   *
   * @param e 与需要寻找的元素相等的元素
   * @return {number} 此列表中指定元素最后一次出现的索引，如果此列表没有，则为 -1
   * @version 1.0
   */
  public lastIndexOf(e: E): number {
    let index = -1;
    for (let i = this._elements.length - 1; i >= 0; i--) {
      if (equalsTo(e, this._elements[i])) {
        index = i;
        break;
      }
    }
    return index;
  }

  /**
   * 移除此集合中所有与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从集合中被删除的元素相等的元素
   * @return {boolean} 如果有元素从集合中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public remove(e: E): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (equalsTo(e, this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
      }
    }
    return flag;
  }

  /**
   * 移除此列表中指定位置的元素。 将任何后续元素向左移动（从它们的索引中减去一个）。
   *
   * 返回从列表中删除的元素。
   *
   * @param index 需要被删除的索引
   * @return {E} 被删除的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public removeByIndex(index: number): E {
    const newIndex = Collections.accurateIndex(this, index);
    const e = this._elements[newIndex];
    for (let i = newIndex; i < this._elements.length; i++) {
      this._elements[i] = this._elements[i + 1];
    }
    return e;
  }

  /**
   * 移除此列表中第一个与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从列表中被删除的元素相等的元素
   * @return {boolean} 如果有元素从列表中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public removeFirst(e: E): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (equalsTo(e, this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
        break;
      }
    }
    return flag;
  }

  /**
   * 使用过滤器，移除此集合中所有符合过滤器要求的元素。
   *
   * @param filter 一个lambda表达式，当表达式返回true时，表示该元素符合过滤器要求
   * @return {boolean} 如果有元素从集合中被删除，则返回true，否则返回false
   * @throws {UnsupportedOperationException} 此方法不受支持
   * @version 1.0
   */
  public removeIf(filter: (e: E) => boolean): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (filter(this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
      }
    }
    return flag;
  }

  /**
   * 用指定的元素替换此列表中指定位置的元素。
   *
   * @param index 要替换的元素的索引
   * @param e 需要替换的元素
   * @return {E} 原本位于此索引的元素
   * @throws {IndexOutOfBoundException} 元素索引位置超出列表的范围
   * @version 1.0
   */
  public set(index: number, e: E): E {
    const newIndex = Collections.accurateIndex(this, index);
    const old = this._elements[newIndex];
    this._elements[newIndex] = e;
    return old;
  }

  /**
   * 返回此列表中的元素数。
   *
   * @return {number} 返回此列表中的元素数
   * @version 1.0
   */
  public size(): number {
    return this._elements.length;
  }

  /**
   * 对列表中的元素进行升序排序。
   *
   * 若提供了比较器，将使用此比较器进行大小比较，否则使用默认的比较方式。
   *
   * @param comparator 用于比较的比较器
   * @throws {IllegalArgumentException} 如果不给出比较器，存储的元素本身也不支持比较
   * @see Comparator
   * @see ComparableObj
   * @version 1.0
   */
  public sort(comparator?: Comparator) {
    const priorityQueue = new PriorityQueue(this.toArray(), -1, comparator);
    this.clear();

    while (!priorityQueue.isEmpty()) {
      const element = priorityQueue.poll() as E;
      this.add(element);
    }
  }

  /**
   * 返回此列表中指定的 fromIndex（含）和 toIndex（不含）之间的部分的视图。
   *
   * 如果 fromIndex 和 toIndex 相等，则返回的列表为空。
   *
   * 返回的列表是一个克隆列表，因此返回列表中的更改不会反映在此列表中，反之亦然。 返回的列表支持该列表支持的所有列表操作。
   *
   * @param fromIndex 子列表的起始索引（含）
   * @param endIndex 子列表的结束索引（不含）
   * @return {List<E>}此列表中指定范围的克隆列表
   * @throws {IllegalArgumentException} 索引超出范围或者起始索引大于结束索引
   * @version 1.0
   */
  public subList(fromIndex: number, endIndex: number): List<E> {
    const newFrom = Collections.accurateIndex(this, fromIndex);
    const newEnd = Collections.accurateIndex(this, endIndex);
    if (newFrom > newEnd) {
      throw new IllegalArgumentException("from value should smaller than end value.")
    }
    return new ArrayList(this._elements.slice(newFrom, newEnd));
  }

  /**
   * 返回由集合内所有元素组成的数组。
   *
   * 该数组内的元素会是列表中元素的<strong>浅拷贝</strong>，因此后续对列表的操作不会影响到数组的浅层，反之亦然。
   *
   * @return {E[]} 一个由集合内所有元素组成的数组
   * @version 1.0
   */
  public toArray(): E[] {
    return this._elements.slice();
  }

  public toString(): string {
    return this._elements.toString();
  }
}
